/*
https://leetcode-cn.com/problems/sum-of-subarray-ranges/solution/zi-shu-zu-fan-wei-he-by-leetcode-solutio-lamr/
 */
import java.util.Stack;

public class Solution2104 {
    public long subArrayRanges(int[] nums) {
        long ans=0L;
        Stack<int[]> stack=new Stack<>();
        long now=0L;
        for (int i=0;i<nums.length;i++){
            int k=1;
            while (!stack.isEmpty() && stack.peek()[0]<=nums[i]){
                now=now+(long)(nums[i]-stack.peek()[0])*(stack.peek()[1]);
                k=k+stack.peek()[1];
                stack.pop();
            }
            now+=nums[i];
            stack.push(new int[]{nums[i],k});
            ans=ans+now;
        }
        stack=new Stack<>();
        now=0L;
        for (int i=0;i<nums.length;i++){
            int k=1;
            while (!stack.isEmpty() && stack.peek()[0]>=nums[i]){
                now=now-(long)(stack.peek()[0]-nums[i])*(stack.peek()[1]);
                k=k+stack.peek()[1];
                stack.pop();
            }
            now+=nums[i];
            stack.push(new int[]{nums[i],k});
            ans=ans-now;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution2104().subArrayRanges(new int[]{4,-2,-3,4,1}));
    }
}
